Digital video capabilities can be incorporated into a wide range of devices, including digital televisions, digital direct broadcast systems, wireless communication devices, personal digital assistants (PDAs), laptop computers, desktop computers, digital cameras, digital recording devices, cellular or satellite radio telephones, and the like. Digital video devices can provide significant improvements over conventional analog video systems in creating, modifying, transmitting, storing, recording and playing full motion video sequences.
A number of different video encoding standards have been established for encoding digital video sequences. The Moving Picture Experts Group (MPEG), for example, has developed a number of standards including MPEG-1, MPEG-2 and MPEG-4. Other standards include the International Telecommunication Union (ITU) H.263 standard, QuickTime™ technology developed by Apple Computer of Cupertino Calif., Video for Windows™ developed by Microsoft Corporation of Redmond, Wash., Indeo™ developed by Intel Corporation, RealVideo™ from RealNetworks, Inc. of Seattle, Wash., and Cinepak™ developed by SuperMac, Inc. New standards continue to emerge and evolve, including the ITU H.264 standard and a number of proprietary standards.
Many video encoding standards allow for improved transmission rates of video sequences by encoding data in a compressed fashion. Compression can reduce the overall amount of data that needs to be transmitted for effective transmission of video frames. Most video encoding standards, for example, utilize graphics and video compression techniques designed to facilitate video and image transmission over a narrower bandwidth than can be achieved without the compression.
The MPEG standards and the ITU H.263 and ITU H.264 standards, for example, support video encoding techniques that utilize similarities between successive video frames, referred to as temporal or inter-frame correlation, to provide inter-frame compression. The inter-frame compression techniques exploit data redundancy across frames by converting pixel-based representations of video frames to motion representations. In addition, some video encoding techniques may utilize similarities within frames, referred to as spatial or intra-frame correlation, to further compress the video frames.
In order to support compression, a digital video device includes an encoder for compressing digital video sequences, and a decoder for decompressing the digital video sequences. In many cases, the encoder and decoder form an integrated encoder/decoder (CODEC) that operates on blocks of pixels within frames that define the sequence of video images. In the International Telecommunication Union (ITU) H.264 standard, for example, the encoder typically divides a video frame to be transmitted into video blocks referred to as “macroblocks” (MB's) which may comprise 16 by 16 pixel arrays. The ITU H.264 standard supports 16 by 16 video blocks, 16 by 8 video blocks, 8 by 16 video blocks, 8 by 8 video blocks, 8 by 4 video blocks, 4 by 8 video blocks and 4 by 4 video blocks. Other standards may support differently sized video blocks.
For each video block in the video frame, an encoder searches similarly sized video blocks of one or more immediately preceding video frames (or subsequent frames) to identify the most similar video block, referred to as the “best prediction block.” The process of comparing a current video block to video blocks of other frames is generally referred to as motion estimation. Once a “best prediction block” is identified for a video block, the encoder can encode the differences between the current video block and the best prediction block. This process of encoding the differences between the current video block and the best prediction block includes a process referred to as motion compensation. Motion compensation comprises a process of creating a difference block, indicative of the differences between the current video block to be encoded and the best prediction block. Motion compensation usually refers to the act of fetching the best prediction block using a motion vector, and then subtracting the best prediction block from an input block to generate a difference block.
After motion compensation has created the difference block, a series of additional encoding steps are typically performed to encode the difference block. These additional encoding steps may depend on the encoding standard being used. In MPEG4 compliant encoders, for example, the additional encoding steps may include an 8×8 discrete cosine transform, followed by scalar quantization, followed by a raster-to-zigzag reordering, followed by run-length encoding, followed by Huffman encoding. An encoded difference block can be transmitted along with a motion vector that indicates which video block from the previous frame (or subsequent frame) was used for the encoding. A decoder receives the motion vector and the encoded difference block, and decodes the received information to reconstruct the video sequences.
It is highly desirable to simplify and improve the encoding process. To this end, a wide variety of encoding techniques have been developed. Because motion estimation is one of the most computationally intensive processes in video encoding, improvements to motion estimation can provide notable improvements in the video encoding process.
It is desirable to find more efficient and accurate ways in computing motion vectors.